package leetcode.动态规划和贪心;

/**
 * https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
 * 动态规划和贪心
 */
public class Test718最长重复子数组 {
    /*
    解法如下：比较每一行和每一列是否存在相同的值，
    若有就把数组 i、j 位置的值改成 [i-1, j-1] + 1 的值
    同时记录最大的 [i, j] 值

          数组 B
          3 2 1 4 7
   数   1 0 0 1 0 0
   组   2 0 1 0 0 0
    A   3 1 0 0 0 0
        2 0 2 0 0 0
        1 0 0 3 0 0  ===> 看对角线，公共的意思就是要累加对角线

其实动态规划也是一种暴力破解，只不过他会记录上一次计算的状态。
通过如上形式的二维矩阵，可以得到数组A、B之间的最长重复子数组的长度是 3
     */

    public static int findLength(int[] A, int[] B) {
        int ans = 0;
        if (A == null || A.length == 0
                || B == null || B.length == 0)
            return ans;
        // 编写状态转移方程
        int ALength = A.length;
        int BLength = B.length;
        int[][] dp = new int[ALength + 1][BLength + 1];
        for (int i = 1; i <= ALength; i++) {
            for (int j = 1; j <= BLength; j++) {
                if (A[i - 1] == B[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > ans)
                    ans = dp[i][j];
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] A = {1, 2, 3, 2, 1};
        int[] B = {3, 2, 1, 4, 7};
        System.out.println(findLength(A, B));
    }



}
